import com.sun.org.apache.xalan.internal.xsltc.runtime.Operators;
import net.egork.utils.Solver;
import net.egork.utils.io.InputReader;

import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;

public class ROADS implements Solver {
    public void solve(int testNumber, InputReader in, PrintWriter out) {

        int k = in.readInt();
        int n = in.readInt();
        int r = in.readInt();

        int v[] = new int[n + 1];
        Arrays.fill(v, -1);
        Edge e[] = new Edge[r];

        for (int i = 0; i < r; ++i) {
            e[i] = new Edge();
            e[i].u = in.readInt();
            e[i].v = in.readInt();
            e[i].len = in.readInt();
            e[i].cost = in.readInt();
            e[i].next = v[e[i].u];
            v[e[i].u] = i;
        }

        Node temp = new Node(1, 0, 0);
        PriorityQueue<Node> pq = new PriorityQueue<Node>();

        pq.add(temp);
        while (!pq.isEmpty()) {
            temp = pq.poll();
            if (temp.u == n) {
                out.println(temp.len);
                return;
            }
            for (int u = v[temp.u]; u != -1; u = e[u].next) {
                Node ne = new Node(e[u].v, temp.len + e[u].len, temp.cost + e[u].cost);
                if (ne.cost <= k)
                    pq.add(ne);
            }
        }
        out.println(-1);
    }

    class Edge {
        public int u, v, len, cost, next;
    }

    class Node implements Comparable<Node> {
        public int u, len, cost;

        public Node(int u, int len, int cost) {
            this.u = u;
            this.len = len;
            this.cost = cost;
        }

        public int compareTo(Node o) {
            return this.len - o.len;
        }
    }
}

